// https://leetcode.cn/problems/move-zeroes/description/

// 算法思路总结：
// 1. 使用快慢双指针技巧
// 2. fast指针遍历数组寻找非零元素
// 3. slow指针标记下一个非零元素应该放置的位置
// 4. 通过交换操作将非零元素移到数组前部
// 5. 保持非零元素的相对顺序不变
// 6. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        int slow = -1, fast = 0;

        while (fast != nums.size())
        {
            if (nums[fast] != 0)
            {
                ++slow;
                if (slow != fast) swap(nums[slow], nums[fast]);
            }
            ++fast;
        }
    }
};

int main()
{
    vector<int> v1 = {0,1,0,3,12};
    vector<int> v2 = {0};

    Solution sol;
    sol.moveZeroes(v1);
    sol.moveZeroes(v2);

    for (auto& val : v1) cout << val << " ";
    cout << endl;
    for (auto& val : v2) cout << val << " ";
    cout << endl;

    return 0;
}